//二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。
//二叉搜索树（BST）是二叉树的一种，但是只允许在左侧节点存储比父节点小的值，在右侧节点存储比父节点大的值。

import { Compare, defaultCompare } from "./utils";

export class Node<T> {
    //节点值
    public key: T;
    public left: Node<T> | null;
    public right: Node<T> | null;
    public constructor(key: T) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

//二叉树
export class BinarySearchTree<T> {

    protected root: Node<T> | null;
    public constructor() {
        this.root = null;
    }

    public insert(key: T) {
        if (this.root == null) {
            this.root = new Node(key);
        } else {
            this.insertNode(this.root, key);
        }
    }

    public search(key: T) {
        return this.searchNode(this.root, key);
    }

    //通过中序遍历所有节点
    //中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。
    public inOrderTraverse(callBack: Function) {
        this.inOrderTraverseNode(this.root, callBack);
    }

    //通过先序遍历方式遍历所有节点
    //先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。
    public preOrderTraverse(callBack: Function) {
        this.preOrderTraverseNode(this.root, callBack);
    }

    // 通过后序遍历方式遍历所有节点
    //后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小。
    public postOrderTraverse(callBack: Function) {
        this.postOrderTraverseNode(this.root, callBack);
    }

    //返回树中最小的值/键
    public min() {
        return this.minNode(this.root);
    }

    //返回树中最大的值/键
    public max() {
        return this.maxNode(this.root);
    }

    public remove(key: T) {
        this.root = this.removeNode(this.root, key);
    }

    protected insertNode(node: Node<T>, key: T) {
        if (defaultCompare(key, node.key) === Compare.LESS_THAN) {
            if (node.left == null) {
                node.left = new Node(key);
            } else {
                this.insertNode(node.left, key);
            }
        } else {
            if (node.right == null) {
                node.right = new Node(key);
            } else {
                this.insertNode(node.right, key);
            }
        }
    }

    protected inOrderTraverseNode(node: Node<T> | null, callBack: Function) {
        if (node != null) {
            this.inOrderTraverseNode(node.left, callBack);
            callBack(node.key);
            this.inOrderTraverseNode(node.right, callBack);
        }
    }

    protected preOrderTraverseNode(node: Node<T> | null, callBack: Function) {
        if (node != null) {
            callBack(node.key);
            this.preOrderTraverseNode(node.left, callBack);
            this.preOrderTraverseNode(node.right, callBack);
        }
    }

    protected postOrderTraverseNode(node: Node<T> | null, callBack: Function) {
        if (node != null) {
            this.preOrderTraverseNode(node.left, callBack);
            this.preOrderTraverseNode(node.right, callBack);
            callBack(node.key);
        }
    }

    protected minNode(node: Node<T> | null) {
        let current = node;
        while (current != null && current.left != null) {
            current = current.left;
        }
        return current;
    }

    protected maxNode(node: Node<T> | null) {
        let current = node;
        while (current != null && current.right != null) {
            current = current.right;
        }
        return current;
    }

    protected searchNode(node: Node<T> | null, key: T): boolean {
        if (node == null) {
            return false;
        }
        if (defaultCompare(key, node.key) == Compare.LESS_THAN) {
            return this.searchNode(node.left, key);
        } else if (defaultCompare(key, node.key) == Compare.BIGGER_THAN) {
            return this.searchNode(node.right, key);
        } else {
            return true;
        }
    }

    protected removeNode(node: Node<T> | null, key: T) {
        if (node == null) {
            return null;
        }
        if (defaultCompare(key, node.key) == Compare.LESS_THAN) {
            node.left = this.removeNode(node.left, key);
            return node;
        }
        else if (defaultCompare(key, node.key) == Compare.BIGGER_THAN) {
            node.right = this.removeNode(node.right, key);
            return node;
        }
        else {
            // handle 3 special conditions
            // 1 - a leaf node
            // 2 - a node with only 1 child
            // 3 - a node with 2 children

            // case 1
            if (node.left == null && node.right == null) {
                node = null;
                return node;
            }
            // case 2
            if (node.left == null) {
                node = node.right;
                return node;
            } else if (node.right == null) {
                node = node.left;
                return node;
            }

            // case 3
            const aux = this.minNode(node.right) as Node<T>;
            node.key = aux.key;
            node.right = this.removeNode(node.right, aux.key);
            return node;
        }
    }
}
